//These codes is rebuild from "tree.h" by lxd in July sixteenth in 2016
//Of course ,the "tree,h" is also develop by lxd
// Thank for your using!!!
#pragma once
#ifndef TREEX
#include<string.h>
#include<queue>
#include<vector>
#include<algorithm>
template<typename A>
struct nodex
{
	bool have_value;	//if have value
	A content;  		//content is value
	nodex *left;
	nodex *right;
	nodex *parent;
	nodex() :have_value(false),content(NULL),left(NULL), right(NULL),parent(NULL){}

};
template<typename T>
class treex
{
public:
	nodex<T>* root;
	std::vector<nodex<T>*> pool;
	treex()
	{
		root = newnodex();
		pool.push_back(root);
	}
	treex(int i)
	{
		root = newnodex();
		root->content = i;
		root->have_value = true;
		pool.push_back(root);
	}
	~treex()
	{
		for (int i = 0; i<(int)pool.size(); i++)
			delete pool[i];
	}
	bool addnodex(nodex<T>* r, T v, char* s)
	{
		int n = strlen(s);
		nodex<T>* u = r;
		for (int i = 0; i<n; i++)
		{
			if (s[i] == 'L')
			{
				if (u->left == NULL)
					u->left = newnodex(u);
				u = u->left;
				pool.push_back(u);
			}
			else
			{
				if (s[i] == 'R')
				{
					if (u->right == NULL)
						u->right = newnodex(u);
					u = u->right;
					pool.push_back(u);
				}
			}
		}
		if (u->have_value)
			return false;
		u->content = v;
		u->have_value = true;
		return true;
	}
	nodex<T>* newnodex()
	{
		return new nodex<T>();
	}
	nodex<T>* newnodex(nodex<T>* parent)
	{
		nodex<T>* buf=new nodex<T>();
		buf->parent=parent;
		return buf;
	}
	bool bfs(std::vector<T>& ans, nodex<T>* root)
	{
		std::queue<nodex<T>*> q;
		ans.clear();
		q.push(root);
		while (!q.empty())
		{
			nodex<T>* u = q.front();
			q.pop();
			if (!u->have_value)
				return false;
			ans.push_back(u->content);
			if (u->left != NULL)
				q.push(u->left);
			if (u->right != NULL)
				q.push(u->right);
		}
		return true;
	}
	bool XXBLintreex(nodex<T>* root, std::vector<T>& ans)
	{
		ans.push_back(root->content);
		if (root->left != NULL)
			XXBLintreex(root->left, ans);
		if (root->right != NULL)
			XXBLintreex(root->right, ans);
		return true;
	}
	bool ZXBLintreex(nodex<T>* root, std::vector<T>& ans)
	{
		if (root->left != NULL)
			ZXBLintreex(root->left, ans);
		ans.push_back(root->content);
		if (root->right != NULL)
			ZXBLintreex(root->right, ans);
		return true;
	}
	bool HXBLintreex(nodex<T>* root, std::vector<T>& ans)
	{
		if (root->left != NULL)
			HXBLintreex(root->left, ans);
		if (root->right != NULL)
			HXBLintreex(root->right, ans);
		ans.push_back(root->content);
		return true;
	}
	void removenodex(nodex<T>* root)
	{
		if (root == NULL)
		return;
		removenodex(root->left);
		removenodex(root->right);
		delete root;
	}
};
template<typename T>
void createhalfman(treex<T> &t,std::vector<T> &ans)
{
	T s=NULL;
	std::vector<T> buffer=ans;
	sort(buffer.begin(),buffer.end());
	for(int i=0;i<(int)ans.size();i++)
	{
		s+=ans[i];
	}
	t.root->content=s;
	nodex<T>* buf=t.root;
	while(buffer.size()>=2)
	{
		T tbuf=buffer[buffer.size()-1];
		s=s-tbuf;
		if(buffer.size()>2)
		{	
			t.addnodex(buf,tbuf,"L");
			t.addnodex(buf,s,"R");
		}		
		else
		{
			t.addnodex(buf,s,"L");
			t.addnodex(buf,tbuf,"R");
		}
		buf=buf->right;
		buffer.pop_back();
	}
}
template<typename T>
T getWPL(treex<T> &t)
{
	T s=NULL;
	nodex<T>* buf=t.root;
	while(buf->right!=NULL)
	{
		s+=buf->content;
		buf=buf->right;
	}
	return s;
}
template<typename T>
void gethalfmancode(treex<T> &t,T i,std::vector<int> &out)
{
	nodex<T>* buf=t.root;
	int n=1;
	out.clear();
	while(buf->right!=NULL)
	{
		if(buf->left->content==i)
		{
			for(int j=1;j<=n-1;j++)
				out.push_back(1);
			out.push_back(0);
			break;
		}
		if((buf->right->content==i)&&(n==t.pool.size()/2))
		{
			for(int j=1;j<=n;j++)
				out.push_back(1);
			break;
		}
		buf=buf->right;
		n+=1;
	}
 } 
template<typename T>
bool translatehalfmancode(nodex<T>* r, T &v, std::vector<int> &s)
{
	int n =(int)s.size();
	nodex<T>* u = r;
	for (int i = 0; i<n; i++)
	{
		if (s[i] == 0)
		{
		if(u->left!=NULL)
			u = u->left;
		else
			return false;	
		}
		else
		{
			if (s[i] == 1)
			{
				if (u->right != NULL)
					u = u->right;
				else
					return false;
			}
		}
	}
	if (u->have_value)
		v=u->content;
	else
		return false;
	return true;
}
#endif
